Search for: All records

Breadth-First Search (BFS) is a fundamental graph traversal algorithm in a level-by-level pattern. It has been widely used in real-world applications, such as social network analysis, scientific computing, and web crawling. However, achieving high performance for BFS on large-scale graphs remains a challenging task due to irregular memory access patterns, diverse graph structures, and the necessity for efficient parallelization. This paper addresses these challenges by designing a highly optimized parallel BFS implementation based on the top-down and bottom-up traversal strategies. It further integrates several key innovations, including graph typea-ware computation strategy selection, graph pruning, twolevel bottom-up, and efficient parallel implementation. We evaluate our method on 11 diverse graphs in terms of size, diameter, and density. On a CPU server with 48 threads, our method achieves an average speedup of 9.5x over the serial BFS implementation. Also, on a synthetic dense graph, our method processes 9.3 billion edges per second, showing its efficiency in dense graph traversal. 

The single-source shortest path (SSSP) problem is essential in graph theory with applications in navigation, biology, social networks, and traffic analysis. The  -Stepping algorithm enhances parallelism by grouping vertices into "buckets" based on their tentative distances. However, its performance depends on values and graph properties. This paper introduces an adaptive parallel Delta-Stepping implementation with three innovations: neighbor reordering, bucket fusion, and graph type-aware selection. Tested on 11 diverse graphs, it achieves an average 7.1× speedup over serial Dijkstra’s algorithm on a 48-thread CPU server. 

The testbed presented in this study supplies various devices to emulate a smart home. The paper highlights how devices can be connected and programmed to perform functions using an application programming interface. Remote-controlled robots in the testbed enable a user to manipulate, monitor, and configure home-based Internet-of-Things (IoT) technologies. The paper describes the equipment used in the testbed, including a wireless security camera, a smart lock, a climate sensor, and two types of robots. Security measures implemented in the testbed are also discussed. Several application scenarios are presented and analyzed on how they were accomplished to demonstrate the functionalities. The smart home testbed is a useful resource for education and development, as it allows for sufficient performance using a single control point.